package leetcode.code1138;

public class Solution {

	String[] board = new String[] { "abcde", "fghij", "klmno", "pqrst", "uvwxy", "z" };

	public String alphabetBoardPath(String target) {
		int c = 'a';
		int x[] = new int[128];
		int y[] = new int[128];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length(); j++, c++) {
				x[c] = i;
				y[c] = j;
			}
		}
		int last = 'a';
		char[] to = target.toCharArray();
		StringBuffer ans = new StringBuffer();
		for (int i = 0; i < to.length; i++) {
			int t = to[i];
			if (t == last) {
				ans.append('!');
				continue;
			}
			if (last == 'z') {
				ans.append('U');
				last = 'u';
			}
			int x1 = x[last], y1 = y[last];
			if (t == 'z') {
				t = 'u';
			}
			int x2 = x[t], y2 = y[t];
			int mx = x2 - x1, my = y2 - y1;
			if (mx != 0) {
				if (mx > 0) {
					ans.append("D".repeat(mx));
				} else {
					ans.append("U".repeat(-mx));
				}
			}
			if (my != 0) {
				if (my > 0) {
					ans.append("R".repeat(my));
				} else {
					ans.append("L".repeat(-my));
				}
			}
			if (to[i] == 'z') {
				ans.append("D");
			}
			ans.append('!');
			last = to[i];
		}
		return ans.toString();
	}
}
